home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_src.lha / LEDA-3.1c-source / src / plane / _ps_tree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-17  |  17.6 KB  |  684 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _ps_tree.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. //--------------------------------------------------------------------
  17. //  
  18. //  Priority Search Trees
  19. //
  20. //  Renate Lassen   (1990)
  21. //
  22. // Implementation follows
  23. // Kurt Mehlhorn: Data Structures and Algorithms 3, section III.5.1.2
  24. //
  25. // -------------------------------------------------------------------
  26.  
  27. #include <LEDA/impl/ps_tree.h>
  28.  
  29.  
  30. // -------------------------------------------------------------
  31. // member functions
  32. // -------------------------------------------------------------
  33.  
  34. // -------------------------------------------------------------
  35. // lrot() , rrot() , ldrot() , rdrot()
  36. // Rotationen am Knoten p
  37.  
  38. void ps_tree::lrot(ps_item p, ps_item q)
  39. { 
  40.   x_typ xh ,yh;
  41.  
  42. //  cout << "lrot\n";
  43. //  cout << "p :" << p->split_value_x() << "\n";
  44. //  cout << "q :" << q->split_value_x() << "\n";
  45.   ps_item h = p->sohn[right];
  46. //  cout << "h :" << h->split_value_x() << "\n";
  47.   xh = h->x_value();
  48.   yh = h->y_value();
  49.   
  50.   p->sohn[right] = h->sohn[left];
  51.   h->sohn[left] = p;
  52.    
  53.   if (!q) root=h;
  54.   else
  55.   {
  56.    if ( p == q->sohn[left] )   q->sohn[left]=h;
  57.    else q->sohn[right]=h;
  58.   }; 
  59.   
  60.   h->x_val = p->x_value();
  61.   h->y_val = p->y_value();
  62.   p->x_val = p->y_val = 0;
  63.  
  64.   if (cmp(xh,yh,h->split_value_x(),h->split_value_y())>0)  
  65.       sink(h->sohn[right],xh,yh);
  66.   else  sink(p->sohn[right],xh,yh); 
  67.     
  68.   fill(p);
  69.   
  70.   p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  71.   h->gr=p->groesse()+h->sohn[right]->groesse();
  72. }
  73.  
  74. void ps_tree::rrot(ps_item p, ps_item q)
  75. { 
  76.   x_typ xh, yh;
  77.   
  78.   //cout << "rrot\n"; 
  79.  // cout << "p :" << p->split_value_x() << "\n";
  80.  // cout << "q :" << q->split_value_x() << "\n";
  81.   ps_item h = p->sohn[left];
  82.  // cout << "h :" << h->split_value_x() << "\n";
  83.   xh=h->x_value();
  84.   yh=h->y_value();
  85.   
  86.   p->sohn[left] = h->sohn[right];
  87.   h->sohn[right] = p;
  88.  
  89.   if (!q) root=h;
  90.   else
  91.   {
  92.    if ( p == q->sohn[left] ) q->sohn[left] = h;
  93.    else q->sohn[right] = h; 
  94.   };
  95.  
  96.   h->x_val = p->x_value();
  97.   h->y_val = p->y_value();
  98.   p->x_val = p->y_val = 0;
  99.   
  100.   if (cmp(xh,yh,h->split_value_x(),h->split_value_y())<=0)  
  101.       sink(h->sohn[left],xh,yh);
  102.   else sink(p->sohn[left],xh,yh);
  103.   
  104.   fill(p);
  105.  
  106.   p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  107.   h->gr=p->groesse()+h->sohn[left]->groesse();
  108. }
  109.  
  110. void ps_tree::ldrot(ps_item p, ps_item q)
  111. { 
  112.     
  113.   //cout << "ldrot\n";
  114.   ps_item h = p->sohn[right];
  115.   ps_item t = h->sohn[left];
  116.   rrot(h,p);
  117.   lrot(p,q);
  118.  // cout << "p:" << p->split_value_x() << "\n";
  119.  // cout << "h:" << h->split_value_x() << "\n";
  120. }
  121.  
  122. void ps_tree::rdrot(ps_item p, ps_item q)
  123. {
  124.  
  125.   //cout << "rdrot\n";
  126.   ps_item h = p->sohn[left];
  127.   ps_item t = h->sohn[right];
  128.   lrot(h,p);
  129.   rrot(p,q);
  130.  // cout << "p:" << p->split_value_x() << "\n";
  131.   //cout << "h:" << h->split_value_x() << "\n";
  132.   //cout << "t:" << t->split_value() << "\n";
  133. }
  134.  
  135. // ------------------------------------------------------------------
  136. // fill(ps_item)
  137. // fuellt Knoten bei Rotation wieder auf 
  138.   
  139. void ps_tree::fill(ps_item p)
  140. {
  141.  
  142.  int leer=0;
  143.  int diff=0;
  144.  //cout << "fill\n";
  145.  while (!p->blatt() && leer!=1)
  146.  {
  147.   diff=cmp(p->sohn[left]->y_value(),p->sohn[right]->y_value()); 
  148.   //cout << "diff = " << diff << "\n";
  149.   if (diff==0) leer=1;                                           // Kinder von p gefuellt ?
  150.   else if ( (diff<0 && p->sohn[left]->y_value()!=0) 
  151.             || (diff>0 && p->sohn[right]->y_value()==0))
  152.        {
  153.         p->x_val = p->sohn[left]->x_value();
  154.         p->y_val = p->sohn[left]->y_value();
  155.         p->sohn[left]->x_val = p->sohn[left]->y_val = 0;   
  156.   //cout <<"gefuellt von links :"<<p->split_value()<<":"<<p->x_value()<<":"<<p->y_value()<<"\n";
  157.         p = p->sohn[left];
  158.        }
  159.        else if ( (diff>0 && p->sohn[right]->y_value()!=0) 
  160.                  || (diff<0 && p->sohn[left]->y_value()==0)) 
  161.             {
  162.             p->x_val = p->sohn[right]->x_value();
  163.             p->y_val = p->sohn[right]->y_value();
  164.             p->sohn[right]->x_val = p->sohn[right]->y_val = 0;   
  165.             p->sohn[right]->x_val = p->sohn[right]->y_val =0;
  166.             p = p->sohn[right];
  167.             };
  168.  };
  169. }
  170.  
  171. // ------------------------------------------------------------------
  172. // sink() 
  173. // laesst Paar (x,y) im Unterbaum mit Wurzel p herabsinken.
  174.    
  175. ps_item ps_tree::sink(ps_item q, x_typ x, x_typ y)
  176. {
  177.  x_typ xh, yh, xneu=x;
  178.  x_typ yneu=y;
  179.  ps_item p =q;
  180.  ps_item inserted; 
  181.  
  182.  while(!p->blatt() && cmp(p->x_value(),0)!=0)
  183.  {
  184.   //cout << "sink\n";
  185.   //cout << p->split_value_x() << ":" << p->split_value_y() <<":"<< p->x_value() << ":" << p->y_value() <<"\n";
  186.   if (cmp(p->y_value(),0)!=0 && cmp(y,p->y_value())<0)
  187.   {                                                    // Tausch
  188.    xh=p->x_value();
  189.    yh=p->y_value();
  190.    p->x_val=x;
  191.    p->y_val=y;
  192.    x=xh;
  193.    y=yh;
  194.    if (cmp(p->x_value(),xneu)==0 && cmp(p->y_value(),yneu)==0) inserted=p;
  195.   //cout << "inserted in Tausch\n";
  196.   //cout << inserted->split_value() <<":"<< inserted->x_value() << ":" << inserted->y_value() <<"\n";
  197.   };
  198.   //cout << "hallo\n";
  199.   if (cmp(x,y,p->split_value_x(),p->split_value_y())<=0)   p=p->sohn[left];
  200.   else 
  201.   {
  202.    p=p->sohn[right]; 
  203.   //cout << p->split_value_x() << ":" << p->split_value_y() <<":"<< p->x_value() << ":" << p->y_value() <<"\n";
  204.   };
  205.  };
  206.  p->x_val=x;
  207.  p->y_val=y;
  208.  if (cmp(p->x_value(),xneu)==0 && cmp(p->y_value(),yneu)==0) inserted=p;
  209.  // cout << "inserted" << inserted->split_value_y() <<":"<< inserted->x_value() << ":" << inserted->y_value() <<"\n";
  210.  return inserted;
  211. }
  212.  
  213. // ------------------------------------------------------------------
  214. // search(x_typ,x_typ)
  215. // sucht Knoten, der das Paar (x,y) enthaelt,
  216. // oder Blatt, an dem neues Blatt fuer x angehaengt werden soll.
  217.  
  218.  
  219. ps_item ps_tree::search(x_typ x,x_typ y)
  220. {
  221.  ps_item p = root;
  222.  ps_item q = 0;
  223.  
  224. // cout << "search\n";
  225.  if (root->blatt())
  226.  {
  227.   st.push(root);
  228.   return p;
  229.  }
  230.  else
  231.  {
  232.   st.push(p);
  233.   while ( !p->blatt() && p!=0 )
  234.   {
  235.    if ( cmp(x,p->x_value())==0 && cmp(y,p->y_value())==0) 
  236.    {
  237.     p=0;
  238.    }
  239.    else 
  240.    { 
  241.     if ( cmp(x,y,p->split_value_x(),p->split_value_y())<=0 ) p=p->sohn[left];
  242.     else p=p->sohn[right]; 
  243.     st.push(p);
  244.    }
  245.   }
  246.   return p;
  247.  }
  248. }  
  249.  
  250.   
  251. // ------------------------------------------------------------------
  252. // locate(x_typ x,x_typ y)
  253. // gibt Knoten oder Blatt mit Inhalt (x,y), falls existiert,
  254. //                                      0 , sonst.
  255.  
  256. ps_item ps_tree::locate(x_typ x,x_typ y)
  257. {
  258.  ps_item p = root;
  259.  ps_item q = 0;
  260.  
  261.  //cout << "locate\n";
  262.  while ( q==0 && p!=0 && cmp(y,p->y_value())>=0 )
  263.  {
  264.   st.push(p);
  265.   if ( cmp(x,p->x_value())==0 && cmp(y,p->y_value())==0) 
  266.   {
  267.    q=p;
  268.   }
  269.   else 
  270.   { 
  271.    if ( cmp(x,y,p->split_value_x(),p->split_value_y())<=0 ) p=p->sohn[left];
  272.    else p=p->sohn[right]; 
  273.   }
  274.  }
  275.  return q;
  276. }
  277.  
  278. // ------------------------------------------------------------------
  279. // delleaf(ps_item)
  280. // loescht Blatt von Paar (x,y) und Vater des Blattes.
  281. // ( Zwei Blaetter mit gemeinsamen Vater sind nie beide gefuellt. )
  282.   
  283. void ps_tree::delleaf(ps_item q)
  284. {
  285.  ps_item p;    
  286.  ps_item t;    
  287.  ps_item father;
  288.  x_typ xh,yh;
  289.  
  290.  //cout << "delleaf\n";
  291.  q->x_val=0;
  292.  q->y_val=0;
  293.  p=st.pop();
  294.  father=st.pop();
  295.  if (q==father->sohn[left] ) father->sohn[left]=0;
  296.  else father->sohn[right]=0;
  297.  delete (q);                                           // loescht Blatt
  298.  t= st.empty() ? 0 : st.top();
  299.  xh=father->x_value();
  300.  yh=father->y_value();
  301.  //cout << "xh: " << xh << "\n";
  302.  //cout << "yh: " << yh << "\n";
  303.   
  304.  if ( father->sohn[left]!=0) q=father->sohn[left];
  305.  else q=father->sohn[right];
  306.  if (t!=0)
  307.  {
  308.   if (father==t->sohn[left])  t->sohn[left]=q;
  309.   else  t->sohn[right]=q;
  310.  }
  311.  else root=q;
  312.  delete(father);                                       // loescht Vater
  313.  
  314.  //cout << "q-x_value: " << q->x_value() << "\n";
  315.  //cout << "q-y_value: " << q->y_value() << "\n";
  316.  //cout << "q-split_value: " << q->split_value() << "\n";
  317.  sink(q,xh,yh);
  318. }
  319.   
  320. // ------------------------------------------------------------------
  321. // insert(x_typ x,x_typ y)
  322. // fuegt ein neues Item (x,y) in den Baum ein
  323. //                 , falls noch nicht vorhanden, 
  324. // Fehlermeldung   ,sonst
  325. // gibt Zeiger auf eingefuegtes Blatt zurueck
  326.  
  327. ps_item ps_tree::insert(x_typ x,x_typ y)
  328. { 
  329.  ps_item p;
  330.  ps_item t;
  331.  ps_item father;
  332.  
  333.  if (!root)                                     // neuer Baum
  334.  {  
  335.   ps_item p=new ps_node(x,y,x,y);
  336.   root=p; 
  337.   anzahl=1; 
  338.   return p;
  339.  }
  340.  else
  341.  {
  342.   p=search(x,y);
  343.   //cout << "p-x_value: " << p->x_value() << "\n";
  344.   //cout << "p-y_value: " << p->y_value() << "\n";
  345.   //cout << "p-split_value_x: " << p->split_value_x() << "\n";
  346.   //cout << "p-split_value_y: " << p->split_value_y() << "\n";
  347.   
  348.   if (p==0)
  349.   {
  350.    error_handler(0,"point already there !");   // Warnung
  351.    st.clear();
  352.    return p;
  353.   }
  354.   else
  355.   {
  356.    ps_item q = new ps_node(0,0,p->split_value_x(),p->split_value_y());   
  357.    ps_item w = new ps_node(0,0,x,y);           // zwei neue Blaetter
  358.   //cout << "q-x_value: " << q->x_value() << "\n";
  359.   //cout << "q-y_value: " << q->y_value() << "\n";
  360.   //cout << "q-split_value_x: " << q->split_value_x() << "\n";
  361.   //cout << "q-split_value_y: " << q->split_value_y() << "\n";
  362.   //cout << "w-x_value: " << w->x_value() << "\n";
  363.   //cout << "w-y_value: " << w->y_value() << "\n";
  364.   //cout << "w-split_value_x: " << w->split_value_x() << "\n";
  365.   //cout << "w-split_value_y: " << w->split_value_y() << "\n";
  366.    if(cmp(p->split_value_x(),p->split_value_y(),x,y)<=0)
  367.    {
  368.     p->sohn[left]=q; 
  369.     p->sohn[right]=w; 
  370.    }
  371.    else
  372.    {
  373.     p->split_val[0] = x;
  374.     p->split_val[1] = y;
  375.     p->sohn[left]=w;
  376.     p->sohn[right]=q;
  377.    } 
  378.                    
  379.   //cout << "p-x_value: " << p->x_value() << "\n";
  380.   //cout << "p-y_value: " << p->y_value() << "\n";
  381.   //cout << "p-split_value_x: " << p->split_value_x() << "\n";
  382.   //cout << "p-split_value_y: " << p->split_value_y() << "\n";
  383.    while (!st.empty())                          // rebalancieren
  384.    { 
  385.     t=st.pop();
  386.    // cout << "stack\n";
  387.     father = st.empty() ? 0 : st.top();
  388.     t->gr++;  
  389.     float i = t->bal();
  390.   
  391.     //cout << "i" << i << "\n";
  392.     if (i < alpha)
  393.     {
  394.      if (t->sohn[right]->bal()<=d) lrot(t,father);
  395.      else ldrot(t,father);
  396.     }
  397.     else if (i>1-alpha) 
  398.     {
  399.       if (t->sohn[left]->bal() > d ) rrot(t,father);
  400.       else rdrot(t,father);
  401.     }
  402.    }
  403.    p = sink(root,x,y);
  404.    //cout<< p->split_value() <<":"<< p->x_value() << ":" << p->y_value() <<"\n";
  405.    return p;
  406.   }
  407.  } 
  408. }
  409. // ------------------------------------------------------------------
  410. // del()
  411. // loescht Item it im Baum mit x_value(it) = x ,
  412. //                             y_value(it) = y , falls existiert
  413. //         und gibt Zeiger auf it zurueck
  414. // 0 , sonst
  415.  
  416. ps_item ps_tree::del(x_typ x,x_typ y)
  417. { 
  418.  ps_item p;
  419.  ps_item t;
  420.  ps_item father;
  421.  ps_item deleted = new ps_node(x,y,0,0);
  422.  
  423.  if (root==0) 
  424.  {
  425.   error_handler(0,"Tree is empty");
  426.   return 0;                                          // leerer Baum
  427.  }
  428.  else
  429.  {
  430.   p=locate(x,y);
  431.   //cout << "located:"<<p->split_value()<<"\n";
  432.   if (p==0) 
  433.   {
  434.    error_handler(0,"Pair is not in tree ");
  435.    st.clear();
  436.    return 0;                                         // Paar nicht im Baum
  437.   }
  438.   else
  439.   { 
  440.    if (p->blatt()) 
  441.    {
  442.     if (p==root)
  443.     {
  444.      error_handler(0,"Root is deleted.");
  445.      p=st.pop();
  446.      root=0;
  447.      anzahl=0;
  448.      return p;                                       // Wurzel geloescht
  449.     } 
  450.     else
  451.     {
  452.      delleaf(p);                                 // (x,y) steht in einem Blatt
  453.     }
  454.    }
  455.    else                                          // (x,y) steht in einem Knoten
  456.    {
  457.     p->x_val = p->y_val = 0;
  458.     fill(p);
  459.     while (!p->blatt())                               // Knoteninhalt loeschen
  460.     {                                                 // und neu auffuellen
  461.      if (cmp(x,y,p->split_value_x(),p->split_value_y())<=0) p=p->sohn[left];
  462.      else p=p->sohn[right];
  463.      st.push(p);
  464.     };
  465.     
  466.     delleaf(p);                                    // loescht zugehoeriges Blatt
  467.    }
  468.  
  469.    while (!st.empty())                                 // rebalancieren
  470.    { 
  471.     t = st.pop();
  472.     //cout << "stack\n";
  473.     //cout << t->split_value()<<":"<<t->x_value()<<":"<<t->y_value()<<"\n";
  474.     father = st.empty() ? 0 : st.top() ;
  475.     t->gr--;              
  476.     float i=t->bal();
  477.     //cout << "i :" << i << "\n";
  478.     if (i<alpha)
  479.     { 
  480.      if (t->sohn[right]->bal() <= d) lrot(t,father);
  481.      else ldrot(t,father);
  482.     }
  483.     else if (i>1-alpha)
  484.     { 
  485.      if(t->sohn[left]->bal() > d) rrot(t,father);
  486.      else rdrot(t,father);
  487.     }
  488.    }
  489.    return(deleted);
  490.   }
  491.  }
  492. } 
  493.    
  494. //-----------------------------------------------------------------------
  495. //enumerate(x1,x2,y0,p)
  496. //gibt alle Punkte (x,y) aus Unterbaum mit Wurzel p
  497. //mit folgender Eigenschaft an :
  498. //  x1 <= x <= x2   &&   y <= y0 
  499. //Voraussetzung : x1 < x2
  500.  
  501. void ps_tree::enumerate(x_typ x1,x_typ x2,x_typ y0,ps_item p)
  502. {
  503.  if (cmp(y0,p->y_value())>=0 && p!=0)
  504.  {
  505.   if (cmp(x1,p->split_value_x())<=0 && cmp(p->split_value_x(),x2)<=0)
  506.   {
  507.    if (cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0)
  508.       cout <<p->split_value_x()<<"("<<p->x_value()<<","<<p->y_value()<<")\n";
  509.    enumerate(x1,x2,y0,p->sohn[left]); 
  510.    enumerate(x1,x2,y0,p->sohn[right]); 
  511.   }
  512.   else if (cmp(p->split_value_x(),x1)<=0) 
  513.        {
  514.         if(cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0)
  515.            cout <<p->split_value_x()<<"("<<p->x_value()<<","<<p->y_value()<<")\n";
  516.         enumerate(x1,x2,y0,p->sohn[right]);
  517.        }
  518.        else if (cmp(x2,p->split_value_x())<=0) 
  519.        {
  520.         if(cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0)
  521.            cout <<p->split_value_x()<<"("<<p->x_value()<<","<<p->y_value()<<")\n";
  522.         enumerate(x1,x2,y0,p->sohn[left]);
  523.        }
  524.  }
  525. }
  526.        
  527. //-----------------------------------------------------------------------
  528. //void pr_ps_tree(ps_item p;int blancs)
  529. //gibt den Baum mit Wurzel p aus
  530.  
  531. void ps_tree::pr_ps_tree(ps_item p,int blancs)
  532. {
  533.  if (p==0)
  534.    { for (int j=1;j<=blancs;j++) cout << " ";
  535.      cout << "NIL\n";
  536.      return;
  537.    }
  538.  else
  539.    { pr_ps_tree(p->sohn[left],blancs+10); 
  540.      for (int j=1;j<=blancs;j++) cout << " ";
  541.      cout << "(" << p->split_value_x() << "," << p->split_value_y() << "):";
  542.      cout << "(" << p->x_value() << "," << p->y_value() << ")\n";
  543.      pr_ps_tree(p->sohn[right],blancs+10); 
  544.    }
  545. }
  546.  
  547. //-----------------------------------------------------------------------
  548. //min_x_in_rect(x1,x2,y0,p)
  549. //sucht nach Paar (x,y) im Unterbaum von p 
  550. //mit folgender Eigenschaft :
  551. //  min { x ; es gibt y, so dass x1<=x<=x2 und y<=y0 } , falls existiert,
  552. //                                                   0 , sonst.
  553.  
  554. pair_item ps_tree::min_x_in_rect(x_typ x1,x_typ x2,x_typ y0,ps_item p)
  555. {
  556.  pair_item  c;
  557.  
  558.  if (p==0)
  559.  {
  560.   return 0;                                   // Baum ist leer.
  561.  }
  562.  else
  563.  {
  564.   c=new pair;
  565.   c->x_pkt=c->y_pkt=0;
  566.   c->valid=false;
  567.   if (cmp(y0,p->y_value())>=0)
  568.   {
  569.    if (!p->blatt())
  570.    {
  571.     if (cmp(x1,p->split_value_x())<=0) 
  572.         c=min_x_in_rect(x1,x2,y0,p->sohn[left]);
  573.     if (!c->valid && cmp(p->split_value_x(),x2)<0) 
  574.         c=min_x_in_rect(x1,x2,y0,p->sohn[right]);
  575.    }
  576.    if (cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0 
  577.        && cmp(p->y_value(),y0)<=0
  578.        && (!c->valid || cmp(p->x_value(),c->x_pkt)<0)     )
  579.    {
  580.     c->x_pkt=p->x_value();  
  581.     c->y_pkt=p->y_value();  
  582.     c->valid=true;
  583.    }
  584.   }
  585.   return c;
  586.  }
  587. }
  588.  
  589. //-----------------------------------------------------------------------
  590. //max_x_in_rect(x1,x2,y0,p)
  591. //sucht nach Paar (x,y) im Unterbaum von p 
  592. //mit folgender Eigenschaft :
  593. //  max { x ; es gibt y, so dass x1<=x<=x2 und y<=y0 } , falls existiert,
  594. //                                                   0 , sonst.
  595.  
  596. pair_item ps_tree::max_x_in_rect(x_typ x1,x_typ x2,x_typ y0,ps_item p)
  597. {
  598.  pair_item c;
  599.  
  600.  if (p==0) 
  601.  {
  602.   return 0;                                      // Baum ist leer.
  603.  }
  604.  else
  605.  {
  606.   c=new pair;
  607.   c->x_pkt=c->y_pkt=0;
  608.   c->valid=false;
  609.   if (cmp(y0,p->y_value())>=0)
  610.   {
  611.    if (!p->blatt())
  612.    {
  613.     if (cmp(p->split_value_x(),x2)<=0) 
  614.         c=max_x_in_rect(x1,x2,y0,p->sohn[right]);
  615.     if (!c->valid && cmp(x1,p->split_value_x())<0) 
  616.         c=max_x_in_rect(x1,x2,y0,p->sohn[left]);
  617.    }
  618.    if (cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0 
  619.        && cmp(p->y_value(),y0)<=0
  620.        && (!c->valid || cmp(p->x_value(),c->x_pkt)>0)     )
  621.    {
  622.     c->x_pkt=p->x_value();  
  623.     c->y_pkt=p->y_value();  
  624.     c->valid=true;
  625.    }
  626.   }
  627.   return c;
  628.  }
  629. }
  630.  
  631. //-----------------------------------------------------------------------
  632. //min_y_in_xrange(x1,x2,p)
  633. //sucht Paar (x,y) im Unterbaum von p
  634. //mit folgender Eigenschaft :
  635. // y = min { y ; es gibt x, so dass x1<=x<=x2 } , falls existiert,
  636. //                                            0 , sonst.
  637.  
  638. pair_item ps_tree::min_y_in_xrange(x_typ x1,x_typ x2,ps_item p)
  639. {
  640.  pair_item c1,c2;
  641.  
  642.  if (p==0)
  643.  {
  644.   return 0;                                      // Baum ist leer.
  645.  }
  646.  else
  647.  {
  648.   c1 = new pair;
  649.   c2 = new pair;
  650.   c1->x_pkt=c1->y_pkt=c2->x_pkt=c2->y_pkt=0; 
  651.   c1->valid=c2->valid=false;
  652.   if (cmp(x1,p->x_value())<=0 && cmp(p->x_value(),x2)<=0)
  653.   {
  654.    c1->x_pkt=p->x_value();
  655.    c1->y_pkt=p->y_value();
  656.    c1->valid=true;
  657.   }
  658.   else if (!p->blatt())
  659.   {
  660.    if (cmp(x1,p->split_value_x())<=0) c1=min_y_in_xrange(x1,x2,p->sohn[left]);
  661.    if (cmp(p->split_value_x(),x2)<0)  c2=min_y_in_xrange(x1,x2,p->sohn[right]);
  662.    if (!c1->valid || (c2->valid && cmp(c2->y_pkt,c1->y_pkt)<0)) c1=c2;
  663.   }
  664.   return c1;
  665.  } 
  666. }
  667.  
  668. //-----------------------------------------------------------------------
  669. // Funktion fuer Destruktor
  670. //-----------------------------------------------------------------------
  671.   
  672. void ps_tree::deltree(ps_item p)
  673. {
  674.  if (p)
  675.  {
  676.   if (!p->blatt())
  677.   {
  678.    deltree(p->sohn[left]);
  679.    deltree(p->sohn[right]);
  680.   }
  681.   delete(p);
  682.  }
  683. }
  684.